package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;
import com.cuz.daileetcode.utils.TreeNode;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Day60 {

    /***
     * 完全二叉树节点个数
     */
    public static class NumberOfNodesOfCompleteBinaryTree {

        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            TreeNode treeNode2 = new TreeNode(2);
            TreeNode treeNode3 = new TreeNode(3);
            TreeNode treeNode4 = new TreeNode(4);
            TreeNode treeNode5 = new TreeNode(5);
            TreeNode treeNode6 = new TreeNode(6);
            TreeNode treeNode7 = new TreeNode(6);

            root.left = treeNode2;
            root.right = treeNode3;
            treeNode2.left = treeNode4;
            treeNode2.right = treeNode5;
//            treeNode3.left = treeNode6;

//            treeNode3.right = treeNode7;
            System.out.println(solution1(root));
        }

        public static int solution1(TreeNode root) {
            return process(root, 1);
        }

        private static int process(TreeNode root, int level) {
            if (root == null) {
                return 0;
            }
            //叶子节点 返回1
            if (root.left == null && root.right == null) {
                return 1;
            }
            //左树层数
            int leftTreeLevel = leftTreeMaxLevel(root.left, level + 1);
            //右树层数
            int rightTreeLevel = leftTreeMaxLevel(root.right, level + 1);
            int res;
            //左树是满二叉树
            if (leftTreeLevel == rightTreeLevel) {
                //已知节点个数为
                //    左树节点个数                +当前根节点
                res = ((1 << (leftTreeLevel - level)) - 1) + 1;
                //求解右树节点个数
                res += process(root.right, level + 1);
            } else {
                //左树不满 但是右树满
                //已知节点个数为
                //       右树节点个数                +当前根节点
                res = ((1 << (rightTreeLevel - level)) - 1) + 1;
                //求解左树节点个数
                res += process(root.left, level + 1);
            }
            return res;
        }

        /****
         * 求解当前节点作为根节点
         * 左树最大深度
         * 前提root是完全二叉树
         * 一直向左
         *
         * @param root 根节点
         * @param level 根节点当前在第几次
         * @return 左树最大深度
         */
        private static int leftTreeMaxLevel(TreeNode root, int level) {
            while (root != null) {
                level++;
                root = root.left;
            }
            return level - 1;
        }
    }


    public static class LongestIncreasingSubsequence {

        private static int[] arrRandomGenerate(int len) {
            int[] res = new int[len];
            for (int i = 0; i < len; i++) {
                res[i] = (int) (Math.random() * len * 10);
            }
            return res;
        }

        public static void main(String[] args) {
            for (int i = 0; i < 20; i++) {
                int[] ints = arrRandomGenerate(10);
                int res1 = solution1(ints);
                int res2 = solution2(ints);
                if (res1 != res2) {
                    ArrayUtils.print(ints);
                    System.out.println(res1);
                    System.out.println(res2);
                    break;
                }
            }
//            int[] ints = {95, 91, 38, 58, 25, 39, 74, 3, 1, 75, 100};
//            int x = solution2(ints);
//            int x1 = solution1(ints);
//            System.out.println(x);
//            System.out.println(x1);
        }

        public static int solution1(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int len = nums.length;
            int[] dp = new int[len];
            dp[0] = 1;
            int res = 1;
            for (int index = 1; index < len; index++) {
                int lessThanMaxIndex = maxNumLessThan(nums[index], nums, dp, index - 1);
                if (lessThanMaxIndex == -1) {
                    dp[index] = 1;
                } else {
                    dp[index] = dp[lessThanMaxIndex] + 1;
                }
                res = Math.max(res, dp[index]);
            }
            return res;
        }

        private static int maxNumLessThan(int target, int[] arr, int[] dp, int maxIndex) {
            int res = -1;
            int dpMax=0;
            for (int index = maxIndex; index >= 0; index--) {
                //要小于 target才能递增
                if (arr[index] < target) {
                    //且找 子序列最长的
                    if (dp[index] > dpMax) {
                        res = index;
                        dpMax=dp[index];
                    }
                }
            }
            return res;
        }


        public static int solution2(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int len = nums.length;
            int[] dp = new int[len];
            dp[0] = 1;
            int res = 1;
            int[] end = new int[len];
            Arrays.fill(end, Integer.MAX_VALUE);
            end[0] = nums[0];
            for (int index = 1; index < len; index++) {
                int lessThanMaxIndex = endGetAndUpdate(nums[index], end);
                if (lessThanMaxIndex == -1) {
                    dp[index] = 1;
                } else {
                    dp[index] = lessThanMaxIndex + 1 + 1;
                }
                res = Math.max(res, dp[index]);
            }
            return res;
        }

        /**
         * end数组的含义：end【i】表示，长度为i+1的子序列最小的结尾数是什么
         * <p>
         * 找end数组中小于arr[i]的最大值的下标，
         * 这个下标x表示，arr[i]可以和end[x]即以前的数够长递增子序列，那么dp[i]=x+1,
         * 且构成了长度为x+1的子序列，
         * 所以如果arr[x]<end[x+1]要把end[x+1]更新为arr[i],这个寻找的过程可以用二分。
         *
         * @param target 目标值
         * @param end    end数组
         * @return 下标
         */
        private static int endGetAndUpdate(int target, int[] end) {
            int left = -1;
            int right = end.length;
            while (left < right) {
                int mid = ((right - left + 1) >> 1) + left;
                if (end[mid] > target) {
                    right = mid - 1;
                } else if (end[mid] == target) {
                    return mid - 1;
                } else {
                    left = mid;
                }
            }
            //找小于target最大的元素，找到-1说明不存在 说明target很小,只能构成长度为1的子串 那么更新end[0]
            if (left < 0) {
                end[0] = Math.min(end[0], target);
                return -1;
            } else {
                //找到了 说明target大于end[left] 可以构成left+1+1的序列 更新下 end[left1]
                end[left + 1] = Math.min(end[left + 1], target);
                return left;
            }
        }
    }
}
